

// 完全背包 优化
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param v int整型 
     * @param n int整型 
     * @param nums int整型vector<vector<>> 
     * @return int整型vector
     */

    int NotFull_max(vector<vector<int>>& nums , int v ,int n)
    {
        // 实现不需要装满情况下的最大价值
        
        vector<int> dp(v + 1);
        for(int i = 1; i <= n ; i++)
        {
            int w = nums[i - 1][1] , vp = nums[i - 1][0];
            for(int j = vp ; j <= v ;j++)           // 修改循环的起始位置和条件
                if(j - vp >= 0) dp[j] = max(dp[j] , dp[j - vp] + w);
        }
        return dp[v];
    }

    int Full_max(vector<vector<int>>& nums , int v ,int n)
    {
        // 实现需要恰好装满时 , 最大价值
        vector<int> dp(v + 1);
        for(int i = 1 ; i <= v ; i++)
            dp[i] = -1;
         
        for(int i = 1; i <= n ; i++)
        {
            int w = nums[i - 1][1] , vp = nums[i - 1][0];
            for(int j = vp ; j <= v ;j++)
                if(j - vp >= 0 && dp[j - vp] != -1) dp[j] = max(dp[j] , dp[j - vp] + w);
        }
        return dp[v] == -1 ? 0 : dp[v];
    }



    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {
        vector<int> ret(2);
        ret[0] = NotFull_max(nums, v, n);
        ret[1] = Full_max(nums, v, n);
        return ret;
    }   
};